package com.zk.algorithm;

import com.zk.algorithm.annotation.Amazon;
import com.zk.algorithm.annotation.TouTiao;
import com.zk.algorithm.bean.DoubleListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 类似 LinkedHashMap
 *
 * 淘汰 least recently used 节点
 *
 * - 用 map 充当真正的容器
 * - LinkedHashMap 只是维护一个键的顺序
 */
@TouTiao("https://www.nowcoder.com/discuss/93344?type=2&order=0&pos=56&page=2")
@Amazon("https://www.nowcoder.com/discuss/148246?type=2&order=0&pos=74&page=1")
public class LRUCache {

    private Map<Integer, DoubleListNode> map = new HashMap<>();

    private DoubleListNode head = new DoubleListNode();
    private DoubleListNode tail = new DoubleListNode();

    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;

        this.head.setNext(this.tail);
        this.tail.setPre(this.head);
    }

    /**
     * 将 NODE 移动到双向链表的头部
     *
     * @param key
     * @return
     */
    public int get(int key) {
        if (map.containsKey(key)) {
            DoubleListNode node = map.get(key);
            removeNode(node);
            addToHead(node);
            return node.getVal();
        } else {
            return -1;
        }
    }

    /**
     * 1. 已经存在，移动到链表的头部
     * 2. 容量已满，删除最末尾的那个
     * 3. 一切正常，插入到头部
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            DoubleListNode node = map.get(key);
            removeNode(node);
            if (node.getVal() != value) {
                node.setVal(value);
            }
            addToHead(node);
        } else {
            if (map.size() == capacity) {
                DoubleListNode remove = tail.getPre();
                removeNode(remove);
            }
            DoubleListNode node = new DoubleListNode(key, value);
            addToHead(node);
        }
    }

    private void addToHead(DoubleListNode node) {
        DoubleListNode oldHead = head.getNext();
        head.setNext(node);
        node.setNext(oldHead);
        oldHead.setPre(node);
        node.setPre(head);
        map.put(node.getKey(), node);
    }

    private void removeNode(DoubleListNode node) {
        node.getNext().setPre(node.getPre());
        node.getPre().setNext(node.getNext());
        map.remove(node.getKey());
    }

    public static void main(String...args) {
        LRUCache cache = new LRUCache( 2 /* capacity */ );

        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));       // returns 1
        cache.put(3, 3);    // evicts key 2
        System.out.println(cache.get(2));       // returns -1 (not found)
        cache.put(4, 4);    // evicts key 1
        System.out.println(cache.get(1));       // returns -1 (not found)
        System.out.println(cache.get(3));       // returns 3
        System.out.println(cache.get(4));       // returns 4
    }

}
